Wang B-machine

As presented by Hao Wang (1954, 1957), his basic machine B is an extremely simple computational model equivalent to the Turing machine. It is "the first formulation of a Turing-machine theory in terms of computer-like models" (Minsky (1967) p. 200). With only 4 sequential instructions it is very similar to, but even simpler than, the 7 sequential instructions of the Post-Turing machine. In the same paper, Wang introduced a variety of equivalent machines, including what he called the W-machine, which is the B-machine with an "erase" instruction added to the instruction set.

Description

As defined by Wang (1954) the B-machine has at its command only 4 instructions:

A sample of a simple B-machine instruction is his example (p. 65):

1. *, 2. →, 3. C2, 4. →, 5. ←

He rewrites this as a collection of ordered pairs:

{ ( 1, * ), ( 2, → ), ( 3, C2 ), ( 4, → ), ( 5, ← ) }

Wang's W-machine is simply the B-machine with the one additional instruction

See also

References

"We can now demonstrate the remarkable fact, first shown by Wang [1957], that for any Turing machine T there is an equivalent Turing machine TN that never changes a once-written symbol! In fact, we will construct a two-symbol machine TN that can only change blank squares on its tape to 1's but can not change a 1 back to a blank." Minsky then offers a proof of this.